package leetcode每日一题;

/**
 * 1. 问题描述
 *      给定一个 n×n 的二维矩阵表示一个图像。
 *      将图像顺时针旋转 90 度。
 *      说明：
 *      你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。
 *
 * 2. 算法分析
 *      就是找规律，没啥特别的算法
 *      我的解题思路就是，一层一层的旋转，所谓的层，就是指矩阵的外边界一圈的元素，从外到内
 *      假设当前为第layer层，我们可以得到一下信息
 *      当前层的四个顶角左边：
 *          [layer][layer]            ......          [layer][layer+len-1]
 *
 *
 *          [layer+len-1][layer]      ......          [layer+len-1][layer+len-1]
 *      当前层顶边元素的坐标()：
 *          [layer][layer],[layer][layer+1],[layer][layer+2],...,[layer][layer+len-2],[layer][layer+len-1]
 *
 *      我们的层旋转思路：
 *          遍历顶边的每一个元素，所谓的矩阵旋转就是以当前顶边的某一个点为起点，然后找到剩余三边上的三个点，构成一个倾斜的正方形
 *          假设当前我们以[layer][layer+j]为起点开始旋转，则剩余的三个点的坐标：(顺时针方向)
 *              [layer+j][layer+len-1]
 *              [layer+len-1][layer+len-1-j]
 *              [layer+len-1-j][layer+len-1]
 *
 *      每层的长度变化
 *          len = len - 2(无论矩阵是奇数阶还是偶数阶，上述规律一致)
 *
 *      在纸上画一个草图，非常明显的规律
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class 原地反转图像 {
    public static void main(String[] args) {
        int[][] arr = new int[10][10];
        int[] temp = arr[3];
    }

    public static void rotate1(int[][] matrix) {
        int rowlen = matrix.length; // 矩阵的长度
        int len = matrix.length;
        // 当前为偶数阶矩阵
        for(int layer = 0; layer < len / 2; layer++) {
            //  旋转第layer层
            // 1. 先旋转四个角 [layer][layer]  [layer][layer+rowlen-1]  [][]
            int temp = matrix[layer][layer]; // 记录当前层的第一个左上角元素
            matrix[layer][layer] =  matrix[layer+rowlen-1][layer];
            matrix[layer+rowlen-1][layer] = matrix[layer+rowlen-1][layer+rowlen-1];
            matrix[layer+rowlen-1][layer+rowlen-1] = matrix[layer][layer+rowlen-1];
            matrix[layer][layer+rowlen-1] = temp;
            if(len % 2 == 0 && layer == matrix.length / 2) {
                break;
            }
            // 2. 旋转四个边（此时就不包括两个角）   有问题????????淦
            for(int j = 1; j <= rowlen - 2; j++) {
                int cur = matrix[layer][layer+j]; //记录当前顶边旋转的第j个元素，以这个元素为起点
                matrix[layer][layer+j] = matrix[layer+rowlen-1-j][layer];
                matrix[layer+rowlen-1-j][layer] = matrix[layer+rowlen-1][layer+rowlen-1-j];
                matrix[layer+rowlen-1][layer+rowlen-1-j] = matrix[layer+j][layer+rowlen-1];
                matrix[layer+j][layer+rowlen-1] = cur;
            }
            rowlen -= 2; // 更新下一层的长度
        }
    }

    /**
     * 实际上上述我的代码可以优化，将顶角的旋转加到内层for中可以不需要提出了单独旋转，当时思考的时候是分开思考的
     * @param matrix
     */
    public static void rotate2(int[][] matrix) {
        int rowlen = matrix.length; // 矩阵的长度
        int len = matrix.length;
        // 当前为偶数阶矩阵
        for(int layer = 0; layer < len / 2; layer++) {
            for(int j = 0; j <= rowlen - 2; j++) {
                int cur = matrix[layer][layer+j]; //记录当前顶边旋转的第j个元素，以这个元素为起点
                matrix[layer][layer+j] = matrix[layer+rowlen-1-j][layer];
                matrix[layer+rowlen-1-j][layer] = matrix[layer+rowlen-1][layer+rowlen-1-j];
                matrix[layer+rowlen-1][layer+rowlen-1-j] = matrix[layer+j][layer+rowlen-1];
                matrix[layer+j][layer+rowlen-1] = cur;
            }
            rowlen -= 2; // 更新下一层的长度
        }
    }

    /**
     * leetcode上Sweetie大神提供的神奇的思路（tql8）
     * 按照矩阵的主对角线翻折矩阵，然后反转一行(收尾交换即可做到)  时间复杂度在线性内，我的算法有嵌套for，所以非线性
     * @param matrix
     */
    public void rotate3(int[][] matrix) {
        // 按主对角线进行翻折
        for(int i = 0; i < matrix.length; i++) {
            for(int j = i; j < matrix.length; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }
        // 反转每行
        for(int i = 0; i < matrix.length; i++) {
            // 反转第i行元素
            // [1,2,3] ---> [3,2,1]
            for(int j = 0; j < matrix.length / 2; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[i][matrix.length-j-1];
                matrix[i][matrix.length-j-1] = temp;
            }
        }
    }

}
